package com.wq.struct;

/**
 * @Author: wangqiang20995
 * @Date:2019/2/18
 * @Description:
 * @Resource:
 */
public class ArrayStruct extends Struct{
    private int[] array;
    private int size;

    public ArrayStruct(int length) {
        array = new int[length];
    }

    public void delete(int element) {
        int index = find(element);
        if (index == -1) {
            throw new RuntimeException("元素[" + element + "]不存在");
        }

        for (int i = index; i < array.length; i++) {
            if (i == array.length - 1) {
                this.array[i] = 0;
                break;
            }
            int temp = this.array[i + 1];
            this.array[i] = temp;
        }
    }


    public void insert(int elem) {
        int location = 0;

        // 判断应插入位置的下标
        for (; location < size; location++) {
            if (array[location] > elem)
                break;
        }

        // 将插入下标之后的所有元素后移一位
        for (int i = size; i > location; i--) {
            array[i] = array[i - 1];
        }

        // 插入元素
        array[location] = elem;

        size++;
    }

    private int find(int target) {
        int lowPosition = 0;
        int highPosition = this.array.length - 1;

        int current;

        if (highPosition < 0) {
            return -1;
        }

        while (true) {
            current = (lowPosition + highPosition) / 2;
            if (this.array[current] == target) {//表示要找的这个数刚好是中间这个数或者如果一开始只有两个或者1个的话，返回的都是低位的值
                return current;
            } else if (current == lowPosition) {//高低位之间只有一个或者两个元素（包含高低位）
                if (this.array[highPosition] == target) {
                    return highPosition;
                } else {
                    return -1;
                }
            } else {
                if (this.array[current] > target) {//数组中元素大于两个
                    highPosition = current;
                } else {
                    lowPosition = current;
                }
            }
        }
    }

    public static void main(String args[]) {
        ArrayStruct arrayStruct = new ArrayStruct(5);
        arrayStruct.insert(10);
        arrayStruct.insert(8);
        arrayStruct.insert(19);
        arrayStruct.insert(1);
        arrayStruct.printStruct();
        arrayStruct.delete(8);
        arrayStruct.printStruct();
    }

    @Override
    protected void printStruct() {

        for (Object t : this.array) {
            System.out.printf("%d\t", t);
        }
        System.out.printf("\n");
    }
}
